#include <iostream>

struct ListNode
{
    int val;
    ListNode *next;
    ListNode():val(0), next(nullptr){}
    ListNode(int x):val(x), next(nullptr){}
    ListNode(int x, ListNode *next):val(x), next(next){}
};

//快慢指针
ListNode* removeNthFromEnd(ListNode* head, int n) 
{
    ListNode* dummy_head = new ListNode(0);
    dummy_head->next = head;
    ListNode* fast = dummy_head;
    ListNode* slow = dummy_head;

    while (n-- && fast!=nullptr)
    {
        fast = fast->next;
    }
    
    while (fast->next != nullptr)
    {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;
    return dummy_head->next;
}

void OutPutListNodeVal(ListNode *head)
{
    std::cout<<"[";
    ListNode *cur_node = head;
    while (cur_node != nullptr)
    {
        std::cout<<cur_node->val;
        cur_node = cur_node->next;
        if (cur_node != nullptr)
        {
            std::cout<<", ";
        }
    }
    std::cout<<"]."<<std::endl;
}

void TestCase1()
{
    //case 1
    // 输入：head = [1,2,3,4,5], n = 2
    // 输出：[1,2,3,5]
    ListNode *case1_node0 = new ListNode(1);
    ListNode *case1_node1 = new ListNode(2);
    ListNode *case1_node2 = new ListNode(3);
    ListNode *case1_node3 = new ListNode(4);
    ListNode *case1_node4 = new ListNode(5);
    case1_node0->next = case1_node1;
    case1_node1->next = case1_node2;
    case1_node2->next = case1_node3;
    case1_node3->next = case1_node4;

    ListNode *head = removeNthFromEnd(case1_node0, 2);
    // output
    OutPutListNodeVal(head);
}

void TestCase2()
{
    //case 2
    // 输入：head = [1], n = 1
    // 输出：[]
    ListNode *case2_node0 = new ListNode(1);

    ListNode *head = removeNthFromEnd(case2_node0, 1);
    // output
    OutPutListNodeVal(head);
}

void TestCase3()
{
    //case 3
    // 输入：head = [1,2], n = 1
    // 输出：[1]
    ListNode *case3_node0 = new ListNode(1);
    ListNode *case3_node1 = new ListNode(2);
    case3_node0->next = case3_node1;

    ListNode *head = removeNthFromEnd(case3_node0, 1);
    // output
    OutPutListNodeVal(head);
}

int main()
{
    TestCase1();
    TestCase2();
    TestCase3();
    return 0;
}